//在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。 
//
// 给定一个由整数坐标组成的数组 queens ，表示黑皇后的位置；以及一对坐标 king ，表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。
// 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
//输出：[[0,1],[1,0],[3,3]]
//解释： 
//[0,1] 的皇后可以攻击到国王，因为他们在同一行上。 
//[1,0] 的皇后可以攻击到国王，因为他们在同一列上。 
//[3,3] 的皇后可以攻击到国王，因为他们在同一条对角线上。 
//[0,4] 的皇后无法攻击到国王，因为她被位于 [0,1] 的皇后挡住了。 
//[4,0] 的皇后无法攻击到国王，因为她被位于 [1,0] 的皇后挡住了。 
//[2,4] 的皇后无法攻击到国王，因为她和国王不在同一行/列/对角线上。
// 
//
// 示例 2： 
//
// 
//
// 
//输入：queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
//输出：[[2,2],[3,4],[4,4]]
// 
//
// 示例 3： 
//
// 
//
// 
//输入：queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3]
//,[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[
//0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4]
//输出：[[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= queens.length <= 63 
// queens[i].length == 2 
// 0 <= queens[i][j] < 8 
// king.length == 2 
// 0 <= king[0], king[1] < 8 
// 一个棋盘格上最多只能放置一枚棋子。 
// 
//
// Related Topics 数组 矩阵 模拟 👍 68 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2023-09-14 08:59:51
 * @description 1222.可以攻击国王的皇后
 */
public class QueensThatCanAttackTheKing{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new QueensThatCanAttackTheKing().new Solution();
		int [][]ar={{0,1},{1,0},{4,0},{0,4},{3,3},{2,4}};
		int [] king={0,0};
		  solution.queensAttacktheKing(ar,king);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*从国王出发，模拟八个方向*/
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
		Set<Integer> queenPos=new HashSet<>();
		for (int[] queen : queens) {
			queenPos.add(queen[0]*8+queen[1]);
		}
		List<List<Integer>> res=new ArrayList<>();
		for (int i = -1; i <=1; i++) {
			for (int j = -1; j <=1; j++) {
				if(i==0&&j==0){
					continue;
				}
				int kx=king[0]+i,ky=king[1]+j;
				//向该方向扩散
				while (kx>=0&&kx<8&&ky>=0&&ky<8){
					int pos=kx*8+ky;
					if(queenPos.contains(pos)){
						res.add(Arrays.asList(kx,ky));
						break;
					}
					kx+=i;
					ky+=j;
				}
			}
		}
		return res;
    }
	/*判断皇后是否在四个方向上*/
	public List<List<Integer>> queensAttacktheKing1(int[][] queens, int[] king) {
		Map<Integer, int[]> candidates = new HashMap<Integer, int[]>();
		int kx = king[0], ky = king[1];
		for (int[] queen : queens) {
			int qx = queen[0], qy = queen[1];
			int x = qx - kx, y = qy - ky;
			//在同一行，或者在同一对角线
			if (x == 0 || y == 0 || Math.abs(x) == Math.abs(y)) {
//sgn为符号函数当 x>0 时为 1 0x<0 时为 −1，x=0 时为 0
				//在每个方向上建一个Hash表，以方向为键，比较最近的距离
				int dx = sgn(x), dy = sgn(y);
				int key = dx * 10 + dy;
				//如果当前方向还没有皇后，或者已经保存的该方向上的距离大于当前到国王的距离
				if (!candidates.containsKey(key) || candidates.get(key)[2] > Math.abs(x) + Math.abs(y)) {
					//分别是， x,y坐标，和xy与king差值的绝对值的和表示距离
					candidates.put(key, new int[]{queen[0], queen[1], Math.abs(x) + Math.abs(y)});
				}
			}
		}

		List<List<Integer>> ans = new ArrayList<List<Integer>>();
		for (Map.Entry<Integer, int[]> entry : candidates.entrySet()) {
			int[] value = entry.getValue();
			List<Integer> posList = new ArrayList<Integer>();
			posList.add(value[0]);
			posList.add(value[1]);
			ans.add(posList);
		}
		return ans;
	}

	public int sgn(int x) {
		return x > 0 ? 1 : (x == 0 ? 0 : -1);
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
